package com.example.leetdemo.finash;

import java.util.HashMap;
import java.util.Map;

public class Solution148 {

    public ListNode sortList(ListNode head) {
        ListNode le = head;
        int length = 0;
        while (le != null) {
            length++;
            le = le.next;
        }
        return mergeSort(head, length);
    }

    private ListNode mergeSort(ListNode head, int length) {
        if (length > 1) {
            int min = length / 2, end = length - min;
            ListNode temp = head;
            for (int i = 0; i < min; i++) {
                head = head.next;
            }
            temp = mergeSort(temp, min);
            ListNode second = mergeSort(head, end);

            ListNode first = new ListNode(), t = first;
            while (min > 0 || end > 0) {
                if (min > 0 && end > 0) {
                    if (temp.val > second.val) {
                        first.next = temp;
                        min--;
                        temp = temp.next;
                    } else {
                        first.next = second;
                        end--;
                        second = second.next;
                    }
                } else if (min == 0) {
                    first.next = second;
                    end--;
                    second = second.next;
                } else if (end == 0){
                    first.next = temp;
                    min--;
                    temp = temp.next;
                }
                first = first.next;
            }
            first.next = null;
            return t.next;
        } else {
            return head;
        }
    }

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

}
